Corelab Seminar
2015-2016
Dimitris Sakavalas
Reliable Communication Despite Limited Knowledge
Abstract.
As communication networks grow in size, they become increasingly
vulnerable to component failures. These networks consist of numerous
interacting entities (agents). Since distributed systems have become
popular and widely used in contemporary networking, the provided
solutions need to cope with erroneous and malicious components in the
underlying communication network. Security and reliability issues that
arise have been objects of extensive research in the fields of Secure
Multiparty Computations and Distributed Computing. In our work we
contribute to the realization of fundamental communication primitives
(Reliable Broadcast and Reliable Message Transmission) in an adversarial
distributed environment, by investigating the impact of the network
structure and the agents' topology knowledge level on the achievability
of these tasks. We consider a worst-case (Byzantine) adversary, which
makes the agents misbehave arbitrarily,
Initially, we consider the t-locally bounded adversary model,
introduced in 2004 by Koo, where a fixed upper bound on the number of
corruptions in each agent's neighborhood is imposed. We explore the
tradeoff between the level of topology knowledge and the solvability of
the problem by developing a versatile technique which allows us to
obtain impossibility results for every level of topology knowledge.
Checking the necessary conditions for the solvability of the problem
proves to be NP-hard but along the way we obtain an efficient
2-approximation algorithm for the ad hoc case (where agents only know
their local neighborhood). On the positive, we generalize the
algorithmic idea behind the simple, yet powerful Certified Propagation
Algorithm (CPA), also introduced by Koo in 2004, and propose algorithms,
that match the obtained bounds (unique algorithms) in every case. Thus,
we exactly characterize the classes of graphs in which reliable
communication is possible with respect to topology knowledge. In order
to achieve these we introduced the Partial Knowledge Model in which each
agent knows a part of the network, namely a connected subgraph
containing itself. As a part of the latter contribution, we manage to
settle an open question of Pelc and Peleg (2005) in the affirmative, by
showing that in ad hoc networks, CPA is unique, that is, it can tolerate
as many local corruptions as any other Broadcast algorithm.
Furthermore, we manage to generalize our results in the General
Adversary model of Hirt and Maurer (1997), which subsumes earlier models
by adapting our techniques and algorithms from the t-locally bounded
model. Thus, we devise the first optimally resilient algorithms for
Reliable Broadcast/Message transmission under restricted knowledge and
general adversaries. Finally, we propose the poly-time uniqueness
algorithmic property, which implies that an algorithmic scheme is as
efficient as any other for a certain problem with respect to polynomial
time. We prove our proposed scheme to be poly-time unique in the ad hoc
case. To obtain our latter results we employ, among others, a novel
notion of joining operation on adversary structures, appropriate notions
of separators in unreliable networks, and a self-reducibility property
of the RMT problem.